/****

    activequant - activestocks.eu

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

	
	contact  : contact@activestocks.eu
    homepage : http://www.activestocks.eu

****/
package org.activequant.math.algorithms;

import java.math.BigInteger;

/**
 * Based on http://www.merriampark.com/comb.htm<br>
 * Should be called CombinationGenerator instead as thats what it does. Holds the following associated variables:
 * <ul>
 * <li>a(int[])</li>
 * <li>n(int)</li>
 * <li>r(int)</li>
 * <li>numLeft(BigInteger)</li>
 * <li>total(BigInteger)</li>
 * </ul>
 * <br>
 * <b>History:</b><br>
 *  - [18.03.2007] Created (Erik Nijkamp)<br>
 *
 *  @author Erik Nijkamp
 */
public class PermutationsGenerator {
	/**
	 * private int[] a;
	 */
	private int[] a;
	/**
	 * private int n;
	 */
	private int n;
	/**
	 * private int r;
	 */
	private int r;
	/**
	 * private BigInteger numLeft;
	 */
	private BigInteger numLeft;
	/**
	 * private BigInteger total;
	 */
	private BigInteger total;
	/**
	 * constructs a PermutationsGenerator(should be called CombinationGenerator instead) using the given n(int) and r(int) to set its associated n(int) and r(int).<br/>
	 * Initializes its associated a(int[]) to an array with size r(int) where each element is set to its index: a[]={0,1,2...,(r-1)}<br/>
	 * Sets its associated total(BigInteger) (and numLeft(BigInteger)) with the total number of combinations: C(n,r)=n!/(r!*(n-r)!)
	 * @param n
	 * @param r
	 */
	public PermutationsGenerator(int n, int r) {
		if (r > n || n < 1)
			throw new IllegalArgumentException();
		this.n = n;
		this.r = r;
		a = new int[r];
		BigInteger nFact = getFactorial(n);
		BigInteger rFact = getFactorial(r);
		BigInteger nminusrFact = getFactorial(n - r);
		total = nFact.divide(rFact.multiply(nminusrFact));
		reset();
	}
	/**
	 * <code>1.</code> sets every element in the associated a(int[]) to its index (a[]={0,1,2....})<br/>
	 * <code>2.</code> sets the associated numLeft(BigInteger) with the value of the associated total(BigInteger)
	 */
	public void reset() {
		for (int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		numLeft = new BigInteger(total.toString());
	}
	/**
	 * returns the associated numLeft(BigInteger)
	 * @return
	 */
	public BigInteger getNumLeft() {
		return numLeft;
	}
	/**
	 * returns whether the associated numLeft(BigInteger) is greater than 0
	 * @return
	 */
	public boolean hasMore() {
		return numLeft.compareTo(BigInteger.ZERO) == 1;
	}
	/**
	 * returns the associated total(BigInteger)
	 * @return
	 */
	public BigInteger getTotal() {
		return total;
	}
	/**
	 * Returns a BigInteger representing the factorial of the given n(int)<br/>
	 * <strong>N!= 1*2*...*N</strong>
	 * @param n
	 * @return
	 */
	private static BigInteger getFactorial(int n) {
		BigInteger fact = BigInteger.ONE;
		for (int i = n; i > 1; i--) {
			fact = fact.multiply(new BigInteger(Integer.toString(i)));
		}
		return fact;
	}
	/**
	 * returns a double[] array holding the next combination of r(int) element sunset from the complete n(int) set
	 * @return
	 */
	public int[] getNext() {
		if (numLeft.equals(total)) {
			numLeft = numLeft.subtract(BigInteger.ONE);
			return a;
		}

		int i = r - 1;
		while (a[i] == n - r + i) {
			i--;
		}
		a[i] = a[i] + 1;
		for (int j = i + 1; j < r; j++) {
			a[j] = a[i] + j - i;
		}

		numLeft = numLeft.subtract(BigInteger.ONE);
		return a;

	}
}
